/**
 * @file     threeSum.ts
 * @brief    [15. 三数之和](https://leetcode-cn.com/problems/3sum/)
 * @author   Zhu
 * @date     2022-03-15 11:47
 */

/**
 * 暴力三层循环
 * @param nums
 * @returns
 */
function threeSum(nums: number[]): number[][] {
    const result = [];
    if (nums.length < 3) return [];
    nums.sort((a, b) => a - b); // 先排序，保证重复值是连续的
    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 去重
        for (let j = i + 1; j < nums.length; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue; // 去重
            for (let k = j + 1; k < nums.length; k++) {
                if (k > j + 1 && nums[k] === nums[k - 1]) continue; // 去重
                if (0 === nums[i] + nums[j] + nums[k]) {
                    result.push([nums[i], nums[j], nums[k]]);
                }
            }
        }
    }

    return result;
}

/**
 * 排序 + 双指针
 * @param nums
 * @returns
 */
function threeSum(nums: number[]): number[][] {
    const result: number[][] = [];
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        const min = nums[i];
        if (min > 0) break;
        if (i > 0 && min === nums[i - 1]) continue;
        const target = 0 - min;

        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            const leftNum = nums[left];
            const rightNum = nums[right];
            const sum = leftNum + rightNum;
            if (sum === target) {
                result.push([min, leftNum, rightNum]);
                do {
                    left++;
                } while (left < right && nums[left] === leftNum);
                do {
                    right--;
                } while (left < right && nums[right] === rightNum);
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
    }

    return result;
}
